package arrays.二分查找;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName BinarySearch.java
 * @Description TODO
 * @createTime 2021年03月09日 19:58:00
 */
public class BinarySearch {
    public static void main(String[] args) {

    }

    //无重复的
    public static int binarySearchOne(int[] arr, int target) {
        int length = arr.length;
        int start = 0, end = length - 1, mid = 0;
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            }
        }
        return -1;
    }

    /**
     * todo  存在左边界  1  2  2  2  3  4 应该返回第一个2
     */
    public static int binarySearchTwo(int[] arr, int target) {
        int length = arr.length;
        int start = 0, end = length - 1, mid = 0;
        while (start <= end) {
            mid = start + (end - start) / 2;
            //存在左边界
            if (arr[mid] == target) {
                end = mid - 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            }
        }
        /**
         * 可能存在两种情况
         * 1. 因为上面跳出循环的条件是start>end,而此时可能数组中不存在目标数，而造成数组越界的情况，需要检查是否越界
         * 2. 找到最后都不存在这个数字
         */
        if (start >= arr.length || arr[start] != target) {
            return -1;
        }
        return start;
    }

    //右边界
    public static int binarySearchThree(int[] arr, int target) {
        int length = arr.length;
        int start = 0, end = length - 1, mid = 0;
        while (start <= end) {
            mid = start + (end - start) / 2;
            //存在左边界
            if (arr[mid] == target) {
                start = mid + 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            }
        }
        /**
         * 可能存在两种情况
         * 1. 因为上面跳出循环的条件是start>end,而此时可能数组中不存在目标数，而造成数组越界的情况，需要检查是否越界
         * 2. 找到最后都不存在这个数字
         */
        if (end <0 || arr[end] != target) {
            return -1;
        }
        return start;
    }
}
